package com.lry.basic.algorithm.recursion;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 返回所有的递增子序列
 */
public class SubSequences {
    public static List<List<Integer>> findSubSequences(int[] nums) {
        Set<List<Integer>> ans = new HashSet<>();
        if(null==nums||nums.length==0){
            return new ArrayList<>(ans);
        }
        List<Integer> path = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];

        dfs(0,path,visited,nums,ans);

        return new ArrayList<>(ans);
    }

    private static void dfs(int start, List<Integer> path, boolean[] visited, int[] nums, Set<List<Integer>> ans) {
        if(path.size()>=2){
            ans.add(new ArrayList<>(path));
        }

        for(int i=start;i<nums.length;i++){
            if(!visited[i]){
                if(i>start&&nums[i]==nums[i-1]&&!visited[i-1])
                    continue;
                if(path.isEmpty()||nums[i]>=path.get(path.size()-1)){
                    visited[i] = true;
                    path.add(nums[i]);
                    dfs(i+1,path,visited,nums,ans);
                    visited[i] = false;
                    path.remove(path.size()-1);
                }
            }
        }
    }


    public static void main(String[] args) {
        System.out.println(new SubSequences().findSubSequences(new int[]{1,2,3,1,1,1,1,1}));
    }
}
